一口笔记

常期望安定，还期望即兴。

0%

发表于 更新于

Raydium 是一个 Solana 平台上的 DEX，提供了各种代币的流动性池，为用户提供流动性挖矿、购买代币的功能。为了给 DEX 项目引入流动性池、对接 Raydium 的交换协议，对 raydium 恒定乘积交换合约的源码进行深入学习，这也是 Raydium 上最新的标准 AMM。

Repository: https://github.com/raydium-io/raydium-cp-swap

流动性池状态及创建时的基本流程

流动性池状态定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#[account(zero_copy(unsafe))]
#[repr(packed)]
#[derive(Default, Debug)]
pub struct PoolState {
    /// 使用的配置，主要包括各种费率，控制标志，拥有者 / 受益者 等信息
    pub amm_config: Pubkey,
    /// 流动性池创建者
    pub pool_creator: Pubkey,
    /// Token A 的金库，用来存储流动性 Token 及收益
    pub token_0_vault: Pubkey,
    /// Token B 的金库，用来存储流动性 Token 及收益
    pub token_1_vault: Pubkey,

    /// 流动性池 token 会在存入 A 或 B 时发放
    /// 流动性池 token 可以被提取为对应的 A 或 B
    pub lp_mint: Pubkey,
    /// A 的铸币厂
    pub token_0_mint: Pubkey,
    /// B 的铸币厂
    pub token_1_mint: Pubkey,

    /// A 使用的 Token 程序，比如旧版本或者 2022
    pub token_0_program: Pubkey,
    /// B 使用的 Token 程序
    pub token_1_program: Pubkey,

    /// TWAP 计价账户的地址
    pub observation_key: Pubkey,

    /// 用于 PDA 签名时使用的 bump
    pub auth_bump: u8,
    /// Bitwise representation of the state of the pool
    /// bit0, 1: disable deposit(vaule is 1), 0: normal
    /// bit1, 1: disable withdraw(vaule is 2), 0: normal
    /// bit2, 1: disable swap(vaule is 4), 0: normal
    pub status: u8,

    pub lp_mint_decimals: u8,
    /// mint0 and mint1 decimals
    pub mint_0_decimals: u8,
    pub mint_1_decimals: u8,

    /// True circulating supply without burns and lock ups
    pub lp_supply: u64,
    /// 金库中欠流动性提供者的 A 和 B 的数额.
    pub protocol_fees_token_0: u64,
    pub protocol_fees_token_1: u64,

    pub fund_fees_token_0: u64,
    pub fund_fees_token_1: u64,

    /// The timestamp allowed for swap in the pool.
    pub open_time: u64,
    /// recent epoch
    pub recent_epoch: u64,
    /// padding for future updates
    pub padding: [u64; 31],
}

初始化流动性池的指令函数签名如下：

1
2
3
4
5
6
pub fn initialize(
    ctx: Context<Initialize>, // 上下文
    init_amount_0: u64,       // A 资产初始数额
    init_amount_1: u64,       // B 资产初始数额
    mut open_time: u64,       // 开始交易时间
) -> Result<()>;

初始化流动性池账户定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#[derive(Accounts)]
pub struct Initialize<'info> {
    /// Address paying to create the pool. Can be anyone
    #[account(mut)]
    pub creator: Signer<'info>,

    /// Which config the pool belongs to.
    pub amm_config: Box<Account<'info, AmmConfig>>,

    /// CHECK: pool vault and lp mint authority
    #[account(
        seeds = [
            crate::AUTH_SEED.as_bytes(),
        ],
        bump,
    )]
    pub authority: UncheckedAccount<'info>,

    /// CHECK: Initialize an account to store the pool state
    /// PDA account:
    /// seeds = [
    ///     POOL_SEED.as_bytes(),
    ///     amm_config.key().as_ref(),
    ///     token_0_mint.key().as_ref(),
    ///     token_1_mint.key().as_ref(),
    /// ],
    ///
    /// Or random account: must be signed by cli
    #[account(mut)]
    pub pool_state: UncheckedAccount<'info>,

    /// Token_0 mint, the key must smaller then token_1 mint.
    #[account(
        constraint = token_0_mint.key() < token_1_mint.key(),
        mint::token_program = token_0_program,
    )]
    pub token_0_mint: Box<InterfaceAccount<'info, Mint>>,

    /// Token_1 mint, the key must grater then token_0 mint.
    #[account(
        mint::token_program = token_1_program,
    )]
    pub token_1_mint: Box<InterfaceAccount<'info, Mint>>,

    /// pool lp mint
    #[account(
        init,
        seeds = [
            POOL_LP_MINT_SEED.as_bytes(),
            pool_state.key().as_ref(),
        ],
        bump,
        mint::decimals = 9,
        mint::authority = authority,
        payer = creator,
        mint::token_program = token_program,
    )]
    pub lp_mint: Box<InterfaceAccount<'info, Mint>>,

    /// payer token0 account
    #[account(
        mut,
        token::mint = token_0_mint,
        token::authority = creator,
    )]
    pub creator_token_0: Box<InterfaceAccount<'info, TokenAccount>>,

    /// creator token1 account
    #[account(
        mut,
        token::mint = token_1_mint,
        token::authority = creator,
    )]
    pub creator_token_1: Box<InterfaceAccount<'info, TokenAccount>>,

    /// creator lp token account
    #[account(
        init,
        associated_token::mint = lp_mint,
        associated_token::authority = creator,
        payer = creator,
        token::token_program = token_program,
    )]
    pub creator_lp_token: Box<InterfaceAccount<'info, TokenAccount>>,

    /// CHECK: Token_0 vault for the pool, create by contract
    #[account(
        mut,
        seeds = [
            POOL_VAULT_SEED.as_bytes(),
            pool_state.key().as_ref(),
            token_0_mint.key().as_ref()
        ],
        bump,
    )]
    pub token_0_vault: UncheckedAccount<'info>,

    /// CHECK: Token_1 vault for the pool, create by contract
    #[account(
        mut,
        seeds = [
            POOL_VAULT_SEED.as_bytes(),
            pool_state.key().as_ref(),
            token_1_mint.key().as_ref()
        ],
        bump,
    )]
    pub token_1_vault: UncheckedAccount<'info>,

    /// create pool fee account
    #[account(
        mut,
        address= crate::create_pool_fee_reveiver::id(),
    )]
    pub create_pool_fee: Box<InterfaceAccount<'info, TokenAccount>>,

    /// an account to store oracle observations
    #[account(
        init,
        seeds = [
            OBSERVATION_SEED.as_bytes(),
            pool_state.key().as_ref(),
        ],
        bump,
        payer = creator,
        space = ObservationState::LEN
    )]
    pub observation_state: AccountLoader<'info, ObservationState>,

    /// Program to create mint account and mint tokens
    pub token_program: Program<'info, Token>,
    /// Spl token program or token program 2022
    pub token_0_program: Interface<'info, TokenInterface>,
    /// Spl token program or token program 2022
    pub token_1_program: Interface<'info, TokenInterface>,
    /// Program to create an ATA for receiving position NFT
    pub associated_token_program: Program<'info, AssociatedToken>,
    /// To create a new program account
    pub system_program: Program<'info, System>,
    /// Sysvar for program account
    pub rent: Sysvar<'info, Rent>,
}

初始化流动性池流程如下：

  1. 判断两种资产的 Mint 账户是否合法，判断 AMM 配置中是否关闭创建 Pool。
  2. 设定开始交易时间。
  3. 创建两种资产的金库。
  4. 创建 PoolState 数据账户。
  5. 创建 ObservationState 数据账户。
  6. 将两种初始资产从创建者账户转账到金库账户。
  7. 判断两个金库账户的数额是否合法（实际上只要大于 0 就合法）。
  8. 计算流动性值: $liquidity = \sqrt(amount0 * amount1)$。
  9. 固定锁定 100 个流动性值: let lock_lp_amount = 100
  10. 发放 liquidity - lock_lp_amount 个 LP token 给创建者。
  11. 从创建者账户里收取创建费（lamports）到一个专门存放创建费的账户中（地址硬编码在合约里）。
  12. 初始化流动性池数据的各个字段。

资产交换

资产交换分为两类：

  1. 基于输入资产: 输入资产额度固定，一部分会作为手续费，一部分作为购买资金输入。
  2. 基于输出资产: 输出资产额度固定，需要额外购买一部分输出资产作为手续费，其他作为购买到的资产输出。

基于输入资产

指令函数签名：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
pub fn swap_base_input(
    ctx: Context<Swap>,      // 上下文
    amount_in: u64,          // 输入资产
    minimum_amount_out: u64  // 最小输出资产，由调用者按照当前价格及滑点计算得出
) -> Result<()>;

#[derive(Accounts)]
pub struct Swap<'info> {
    // 交换者
    pub payer: Signer<'info>,

    // 流动性池的金库和流动性 token mint 的权限账户
    /// CHECK: pool vault and lp mint authority
    #[account(
        seeds = [
            crate::AUTH_SEED.as_bytes(),
        ],
        bump,
    )]
    pub authority: UncheckedAccount<'info>,

    /// 用于读取协议费用
    #[account(address = pool_state.load()?.amm_config)]
    pub amm_config: Box<Account<'info, AmmConfig>>,

    /// 流动性池数据账户
    #[account(mut)]
    pub pool_state: AccountLoader<'info, PoolState>,

    /// 用户购买使用的 token ATA，即输入 token 的 ATA
    #[account(mut)]
    pub input_token_account: Box<InterfaceAccount<'info, TokenAccount>>,

    /// 用户希望购买到的 token ATA，即输出 token 的 ATA
    #[account(mut)]
    pub output_token_account: Box<InterfaceAccount<'info, TokenAccount>>,

    /// 接收用户购买使用的 token 的金库
    #[account(
        mut,
        constraint = input_vault.key() == pool_state.load()?.token_0_vault || input_vault.key() == pool_state.load()?.token_1_vault
    )]
    pub input_vault: Box<InterfaceAccount<'info, TokenAccount>>,

    /// 输出用户希望购买到的 token 的金库
    #[account(
        mut,
        constraint = output_vault.key() == pool_state.load()?.token_0_vault || output_vault.key() == pool_state.load()?.token_1_vault
    )]
    pub output_vault: Box<InterfaceAccount<'info, TokenAccount>>,

    /// 输入 token 的程序（可能是 2022）
    pub input_token_program: Interface<'info, TokenInterface>,

    /// 输出 token 的程序（可能是 2022）
    pub output_token_program: Interface<'info, TokenInterface>,

    /// 输入 token 的铸币厂
    #[account(
        address = input_vault.mint
    )]
    pub input_token_mint: Box<InterfaceAccount<'info, Mint>>,

    /// 输出 token 的铸币厂
    #[account(
        address = output_vault.mint
    )]
    pub output_token_mint: Box<InterfaceAccount<'info, Mint>>,

    /// 记录价格的数据账户，用于计算 TWAP 价格 
    #[account(mut, address = pool_state.load()?.observation_key)]
    pub observation_state: AccountLoader<'info, ObservationState>,
}

基于输入的资产交换流程如下：

  1. 检查时间、状态等是否允许交换。
  2. 计算转账（应该指的是向金库中转账）费用，从总的输入费用中减去这部分，将剩余部分 actual_amount_in 作为实际购买资金。
  3. 计算两个金库扣除协议费用和资金费用之后剩余的部分，即实际上提供流动性的两种资金。
  4. 按照上一步计算得到了两种资金，计算两种资金置换另一种的价格，$A / B$ 和 $B / A$，同时转换为 u128 左移 32 位使用定点数来保存精度。
  5. 将第 3 步得到的两种资金额度相乘，得到恒定乘积 $A * B$。
  6. 计算交换结果，包括各种额度、费用。
  7. 将上一步得到的计算结果中的交换后的的源资产额度减去交易费用，再乘以这个结果中交换后的目标资产额度，得到交换后的恒定乘积 $A’ * B’$。
  8. 验证第 6 步计算结果中交换的源资产额度是否等于 actual_amount_in。
  9. 检查第 6 步计算结果中交换得到的目标资产额度减去转账费用之后，是否仍然大于 0 ；同时检查，是否大于等于 minimum_amount_out，如果不满足表示超过滑点限制。
  10. 更新流动性池状态的协议费用及资金费用，用于记录金库中非流动性的部分的额度。
  11. 发送一个 SwapEvent 事件。（为什么？怎么利用？）
  12. 验证交换后的恒定乘积大于等于交换前的恒定乘积，即 $A’ B’ \geq A B$。
  13. 根据计算后的结果，将相应额度的输入资产从用户账户转账到金库账户，将相应额度的输出资产从金库账户转账到用户账户。
  14. 更新观测状态（ObservationState）的值。

基于输出资产

TODO

观测状态 / TWAP 计价器

观测值及观测状态结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#[zero_copy(unsafe)]
#[repr(packed)]
#[derive(Default, Debug)]
pub struct Observation {
    /// The block timestamp of the observation
    pub block_timestamp: u64,
    /// the cumulative of token0 price during the duration time, Q32.32, the remaining 64 bit for overflow
    pub cumulative_token_0_price_x32: u128,
    /// the cumulative of token1 price during the duration time, Q32.32, the remaining 64 bit for overflow
    pub cumulative_token_1_price_x32: u128,
}

#[account(zero_copy(unsafe))]
#[repr(packed)]
#[cfg_attr(feature = "client", derive(Debug))]
pub struct ObservationState {
    /// Whether the ObservationState is initialized
    pub initialized: bool,
    /// the most-recently updated index of the observations array
    pub observation_index: u16,
    pub pool_id: Pubkey,
    /// 固定长度的环形缓冲区，用于循环写入观测记录
    pub observations: [Observation; OBSERVATION_NUM], // OBSERVATION_NUM == 100
    /// padding for feature update
    pub padding: [u64; 4],
}

其中最重要的函数是更新：

1
2
3
4
5
6
pub fn update(
    &mut self,
    block_timestamp: u64,
    token_0_price_x32: u128,
    token_1_price_x32: u128,
);
  1. 该函数将一个 Oracle 观测值写入到当前状态中，并将当前索引自增一模 OBSERVATION_NUM，即循环写入。
  2. 该函数一秒钟最多执行一次。
  3. 将两种资产的当前价格与跟上一个记录的时间差值相乘，即: $Price * \Delta T$。
  4. 然后将上一步求出的两个结果与上一个记录的两个值累加起来 (wrapping_add)，作为新记录的两个值。
  5. 更新索引。

原理

TWAP ，即时间加权平均价格(Time Weighted Average Price)；用来平滑价格波动，减少大宗交易对市场价格的冲击。

计算公式为：

即某个特定时间内的 TWAP 为：每小段时间乘以当时的价格求和，除以总时间。

设计理由（猜测）

我能想到的另外一种方案是：

  1. 观测状态中的每个观测记录，只记录 $Price * \Delta T$ 和时间戳即可。
  2. 当要求某段时间的 TWAP 时，将这段时间的所有记录累加，除以总时长即可，时间复杂度 $O(n)$。
  3. 这样看起来好像可以避免 wrapping_add，源码中不断累加更可能遇到这种情况。

而源码在计算某段时间的 TWAP 时，只需要将最后一个记录的值和第一个记录的值的差除以总时间即可，即这种方案时间复杂度只有 $O(1)$ 。而且实际上 wrapping_add 得到的累加值在相减的时候仍然可以得到正确的结果，只要在这段时间内没有溢出两次就行了。

发表于 更新于

5. 权益证明共识机制

5.1 描述

这个机制是用来：

  1. 快速确认由 PoH 生成器生成的当前序列。
  2. 投票选出下一个 PoH 生成器。
  3. 惩罚不当行为的验证者。

这个算法依赖于所有参与节点在规定超时时间内最终接收到的消息。

5.2 术语

  • 押金(bonds): 验证者在验证交易时的承诺作为抵押的代币。
  • 惩罚机制(slashing): 为解决无利害关系问题提出的方案，当不同的分支被发布时，当前分支可以销毁验证者的押金。
  • 超级多数(super majority): 由押金加权之后，验证者的总票数达到三分之二。这意味着发起攻击的经济成本等同于代币市值的三分之一。

无利害关系问题(Nothing at Stake Problem): 在权益证明系统中，验证者不需要消耗物理资源（如电力），而是依赖于其押金（Stake）。因此，如果网络分叉，验证者可以选择在多个分支上投票，因为这样不会有额外成本。他们会试图最大化收益，而不关心网络的最终一致性。

5.3 质押

用户将代币转账到一个自己名下的质押账户，这笔押金在赎回之前需要保持不动。

质押账户有锁定期，锁定期结束才能赎回。

超级多数确认了质押交易之后，质押才有效。

5.4 投票

  1. PoH 生成器会在预定义好的周期内发布一个自身状态的签名。
  2. 每个质押的身份需要发布一份状态的签名，作为投票。
  3. 投票只有同意票，没有反对票。
  4. 如果在超时时间内，绝对多数达成了共识，这个分支就会被认为是合法的。

5.5 解质押

如果用户未能按时参与投票，质押的币会被标记为“过期”，旨在强制参与者保持活跃，否则将失去投票资格。

N 作为投票失效的次数阈值，会随着过期投票的数量增加而增长，N 的动态调整也可以为网络的自愈能力提供支持，减少对投票延迟的影响。

5.6 选举

  1. 检测到 PoH 生成器故障时，新 PoH 生成器选举就会发生。
  2. 拥有最高投票权重、更高的公钥地址的验证者会被选为新的 PoH 生成器。
  3. 需要超级多数确认，如果在完成确认前新的生成器故障，就重新选择下一个新的 PoH 生成器。
  4. 切换选票时，投票的验证者需要在一个更高的 PoH 序列计数器上投票，否则会触发惩罚。
  5. 会选择一个次级生成器，用于主生成器故障时快速切换。

5.7 选举触发条件

5.7.1 分叉的 Proof of History 生成器

  1. 只有当 PoH 生成器的标识被攻破时，才可能发生分叉。
  2. 分叉的检测依据是同一个 PoH 标识发布了两个不同的历史记录。

5.7.2 运行时异常

  1. Bug、硬件故障、人为错误可能导致生成器生成无效状态，并发布与本地验证者不一致的签名。
  2. 验证者将通过 Gossip 协议发布正确的签名，这一事件将触发新的选举。
  3. 接收无效状态的验证者将收到惩罚。

5.7.3 网络超时

5.8 惩罚

  1. 恶意投票：对两个不同的序列投票，受质押削减惩罚。
  2. 非恶意的竞选序列冲突，投票会被撤销，不会惩罚。
  3. 对 PoH 生成器的无效哈希进行投票，受质押削减惩罚。

5.9 次级选举

  1. 次级选举是在主序列上被提出的。
  2. 在超时时间内通过绝对多数投票，次级生成器就当选了。
  3. 主生成器通过在序列中插入指示交接的消息，来实现软交接。
  4. 如果主生成器发生故障，已当选的次生成器会被作为第一备选。

5.10 可用性

  1. CAP 中 Solana 选择 A 可用性。
  2. 最终一致性：在合理的人类时间范围内保持一定程度的一致性。
  3. 利用 PoH（Proof of History）机制提供了时间的客观测量，结合 PoS 投票记录，可以动态地取消不可用验证者的质押，调整网络的活性和一致性需求。
  4. 在合理的时间内，随着不可用验证者被逐步取消质押，网络可以逐步恢复到满足 2/3 共识的状态，从而达成一致性。

发表于 更新于

PoH (Proof of History) 是⼀种⽤于验证事件之间的顺序和时间流逝的证明。
PoH is a proof for verifying order and passage of time between events.

1. 简介

区块链本质上是一个容错复制状态机。

使用 PoH，网络中的节点可以不依靠其他信任机制验证账本记录的时间流逝。

  • 问题
  1. PoH 如何生成可验证的时间间隔。2. PoH 如何生成可验证的事件执行时间。

2. 提纲

3. 网络设计

  1. 某个节点被选举为领导者（Leader），负责生成历史证明序列（提供网络全局读取一致性以及可验证的时间流逝）。
  2. 领导者搜集用户消息并排序。
  3. 领导者对内存中的交易进行处理，并将交易和签名发送到验证复制节点（Verifier）。
  4. 验证复制节点在其状态副本上执行相同的交易，并发布处理的状态签名，作为交易确认及共识算法投票。

整体网络的交易流向

Leader 选举是基于 PoS 实现的。

4. 历史证明

  1. 历史证明是一个计算序列。
  2. 依赖一个加密的安全函数，无法通过输入预测输出，必须完全执行函数才能生成输出。
  3. 函数在单个核心上按顺序执行，上一步的输出作为下一步输入，定期记录当前输出及执行的次数。
  4. 外部计算机可以通过检查其中的每个序列段来重新计算并验证输出。
  • 问题

原文有 Data can be timestamped into this sequence by appending the data (or a hash of some data) into the state of the function. 这句话里的 timestamped 应该不是传统意义的时间戳的意思，而是某种反映执行顺序(和次数？)的更本质的标记。也就说，这种机制提供了“时间戳“的实现。

4.1 说明

PoH序列

只需要每隔一段时间发布哈希和索引的子集，即：

PoH序列

只要选择的哈希函数是抗冲突的、不可预测结果的，产生的序列就只能由一个计算机线程按顺序计算得到。也就是，如果不从起始值开始计算 N 次，就无法获得索引 N 处的哈希值。

哈希的抗冲突、不可预测性和顺序计算，使得我们能够确定，某段序列的产生过程中发生了时间的流逝。

历史证明序列

4.2 事件时间戳

将数据或数据的哈希通过“组合函数”插入到这个序列中参与计算，则这些附加的数据就拥有了时间顺序。

带数据的历史证明序列

4.3 验证

可以利用多核，同时验证一个序列的多段。N 个核就可以同时验证 N 段。产生一段序列的预期时间如果是 T，验证时使用的核数是 C，则验证这段序列需要的时间只有 T / C。

4.4 横向扩容

两个 PoH 生成节点互相观察对方最近一次的状态，加入自己下一步哈希的数据，实现多个 PoH 链的混合 / 同步。

通过定期同步生成器，每个生成器都可以处理一部分外部流量，整个系统就可以处理更多事件。

  • 问题
  1. 混合的意义是什么，不混合仍然可以横向扩展多个 PoH 链。是为了保证系统整体的一致性，提高防篡改性？

4.5 一致性

为了防止恶意重排序攻击，客户端在创建事件时，需要获取最近的哈希，把该事件挂到某个 PoH 链上，即为事件打上 PoH 的时间戳。

为了防止恶意 PoH 生成器篡改客户端提交的事件关联的哈希，客户端可以提交数据和关联哈希的签名，而不仅仅是数据的签名。

客户端提交数据和最近哈希签名到PoH链

验证时只需验证两点：

  1. 签名是否正确。
  2. 关联的哈希在 PoH 链上是否在当前的事件前面。
1
2
3
4
5
(Signature, PublicKey, hash30a, event3 data) = Event3

Verify(Signature, PublicKey, Event3)

Lookup(hash30a, PoHSequence)

4.6 开销

每秒 4000 个哈希产生 160KB 额外数据。

这些数据，使用 4000 核的 GPU 需要 0.25-0.75 毫秒进行验证。

4.7 攻击

4.7.1 逆序

恶意攻击者需要从第二个事件开始伪造，但是这个延迟已经足够让其他正常节点对于初始序列达成共识。

4.7.2 速度

使用多个 PoH 生成器可以增强抗攻击性。

一个生成器有高带宽，用来接收并混合事件，另一个高速低带宽，定期与高带宽链同步混合，它会生成辅助序列，让攻击者逆序更难。

4.7.3 长程攻击

  • PoH 提供了时间上的不可篡改性。
  • PoRep 提供了存储数据的真实性证明。
  • 两者结合提供了对伪造账本的防御能力。

攻击者不仅需要耗费巨大的时间成本来伪造时间戳，还需要在存储上符合 PoRep 的要求。

发表于 更新于

Pubkey

1
pub struct Pubkey(pub(crate) [u8; 32]);

find_program_address

1
2
3
4
pub fn find_program_address(seeds: &[&[u8]], program_id: &Pubkey) -> (Pubkey, u8) {
    Self::try_find_program_address(seeds, program_id)
        .unwrap_or_else(|| panic!("Unable to find a viable program address bump seed"))
}

try_find_program_address

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
pub fn try_find_program_address(seeds: &[&[u8]], program_id: &Pubkey) -> Option<(Pubkey, u8)> {
    // Perform the calculation inline, calling this from within a program is
    // not supported
    #[cfg(not(target_os = "solana"))]
    {
        let mut bump_seed = [std::u8::MAX]; // 从 std::u8::MAX 开始尝试
        for _ in 0..std::u8::MAX {
            {
                let mut seeds_with_bump = seeds.to_vec();
                seeds_with_bump.push(&bump_seed); // 将 bump 作为种子的最后一部分
                match Self::create_program_address(&seeds_with_bump, program_id) {
                    Ok(address) => return Some((address, bump_seed[0])),
                    Err(PubkeyError::InvalidSeeds) => (),
                    _ => break,
                }
            }
            bump_seed[0] -= 1; // 尝试失败了就减 1 再尝试
        }
        None
    }
    // Call via a system call to perform the calculation
    #[cfg(target_os = "solana")]
    {
        // ...
    }
}

create_program_address

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
pub fn create_program_address(
    seeds: &[&[u8]],
    program_id: &Pubkey,
) -> Result<Pubkey, PubkeyError> {
    if seeds.len() > MAX_SEEDS { // 种子最多有 16 个
        return Err(PubkeyError::MaxSeedLengthExceeded);
    }
    for seed in seeds.iter() {
        if seed.len() > MAX_SEED_LEN { // 每个种子最长 32
            return Err(PubkeyError::MaxSeedLengthExceeded);
        }
    }

    // Perform the calculation inline, calling this from within a program is
    // not supported
    #[cfg(not(target_os = "solana"))]
    {
        let mut hasher = crate::hash::Hasher::default(); // 就是一个 Sha256
        for seed in seeds.iter() {
            hasher.hash(seed);
        }
        // PDA_MARKER 是一个 21 字节长的字符串
        // const PDA_MARKER: &[u8; 21] = b"ProgramDerivedAddress";
        hasher.hashv(&[program_id.as_ref(), PDA_MARKER]);
        let hash = hasher.result();

        if bytes_are_curve_point(hash) { // PDA 账户需要确保不在爱德华曲线上
            return Err(PubkeyError::InvalidSeeds);
        }

        Ok(Pubkey::from(hash.to_bytes()))
    }
    // Call via a system call to perform the calculation
    #[cfg(target_os = "solana")]
    {
        let mut bytes = [0; 32];
        let result = unsafe {
            crate::syscalls::sol_create_program_address(
                seeds as *const _ as *const u8,
                seeds.len() as u64,
                program_id as *const _ as *const u8,
                &mut bytes as *mut _ as *mut u8,
            )
        };
        match result {
            crate::entrypoint::SUCCESS => Ok(Pubkey::from(bytes)),
            _ => Err(result.into()),
        }
    }
}

bytes_are_curve_point

1
2
3
4
5
6
7
8
9
10
pub fn bytes_are_curve_point<T: AsRef<[u8]>>(_bytes: T) -> bool {
    #[cfg(not(target_os = "solana"))]
    {
        curve25519_dalek::edwards::CompressedEdwardsY::from_slice(_bytes.as_ref())
            .decompress()
            .is_some()
    }
    #[cfg(target_os = "solana")]
    unimplemented!();
}

总结

整体流程

  1. 从 [std::u8::MAX] (即 [255]) 开始作为 bump 尝试，值依次递减至 0，bump 就是最后一个种子。
  2. 检查种子数是否不超过 16 (包含 bump，也就是用户能输入的只有 15 个)，所有种子长度不超过 32.
  3. 使用所有种子依次输入 Sha256 进行哈希，然后将 program_id 及一个 21 字节的常量 PDA_MARKER (b"ProgramDerivedAddress") 输入进行哈希。
  4. 计算哈希结果并判断是否在 Curve25519 上，如果不在，表示是合法的 PDA 地址，否则 bump 自减 1 从第二步开始重试。
  5. 如果从 [255] 到 [0] 都找不到，则返回 None / 报错。

Curve25519 是一种特定的爱德华曲线，它设计用于实现高效、安全的 Diffie-Hellman 密钥交换。

发表于 更新于

AccountInfo

solana_program::account_info::AccountInfo

账户信息（AccountInfo），合约中对于账户基本信息的引用（余额和数据可变）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/// Account information
#[derive(Clone)]
#[repr(C)]
pub struct AccountInfo<'a> {
    /// Public key of the account
    pub key: &'a Pubkey,
    /// The lamports in the account.  Modifiable by programs.
    pub lamports: Rc<RefCell<&'a mut u64>>,
    /// The data held in this account.  Modifiable by programs.
    pub data: Rc<RefCell<&'a mut [u8]>>,
    /// Program that owns this account
    pub owner: &'a Pubkey,
    /// The epoch at which this account will next owe rent
    pub rent_epoch: Epoch,
    /// Was the transaction signed by this account's public key?
    pub is_signer: bool,
    /// Is the account writable?
    pub is_writable: bool,
    /// This account's data contains a loaded program (and is now read-only)
    pub executable: bool,
}

Account

anchor_lang::accounts::account::Account

账户（Account），对 AccountInfo 的包装，并能够自动反序列化 T。

1
2
3
4
5
#[derive(Clone)]
pub struct Account<'info, T: AccountSerialize + AccountDeserialize + Clone> {
    account: T,
    info: &'info AccountInfo<'info>,
}

基本功能

  1. 检查 T::owner() 是否等于 info.owner，这就要求 T: Owner。通常使用 #[account] 宏来自动为 T 实现 Owner，并使用 crate::ID() 也就是合约地址作为它的 owner。
  2. 此外，它还会保证 !(Account.info.owner == SystemProgram && Account.info.lamports() == 0)，即账户所有者不是系统程序（必须是非系统合约），并且账户的 SOL 余额不能为 0。

AccountLoader

anchor_lang::accounts::account_loader::AccountLoader

账户加载器，用于按需零拷贝反序列化的提取器，类型 T 需要实现 ZeroCopy。

1
2
3
4
5
#[derive(Clone)]
pub struct AccountLoader<'info, T: ZeroCopy + Owner> {
    acc_info: &'info AccountInfo<'info>,
    phantom: PhantomData<&'info T>,
}

基本功能

load_init: 在初始化时（只能）运行一次，得到一个 RefMut<T>，可读写。
load: 加载只读引用 Ref<T>。
load_mut: 加载读写引用 RefMut<T>。

InterfaceAccount

anchor_lang::accounts::interface_account::InterfaceAccount

接口账户，用来支持 T: Owners 的情况。即有多个程序拥有这种类型的账户数据，引入时是为了支持 token-2022 #2386。

1
2
3
4
5
6
7
#[derive(Clone)]
pub struct InterfaceAccount<'info, T: AccountSerialize + AccountDeserialize + Clone> {
    account: Account<'info, T>,
    // The owner here is used to make sure that changes aren't incorrectly propagated
    // to an account with a modified owner
    owner: Pubkey,
}

基本功能

  1. 检查所有者，即 T::owners().contains(InterfaceAccount.info.owner)。
  2. 同 Account 的第二项。

Interface

anchor_lang::accounts::interface::Interface

接口，用来表示实现了某种接口的程序中的某一个。

1
2
#[derive(Clone)]
pub struct Interface<'info, T>(Program<'info, T>);

TODO: 例子。

Program

anchor_lang::accounts::program::Program

程序，表示一个程序/合约。

1
2
3
4
5
#[derive(Clone)]
pub struct Program<'info, T> {
    info: &'info AccountInfo<'info>,
    _phantom: PhantomData<T>,
}

Signer

anchor_lang::accounts::signer::Signer

签名者，检查 Signer.info.is_signer == true。

1
2
3
4
#[derive(Debug, Clone)]
pub struct Signer<'info> {
    info: &'info AccountInfo<'info>,
}

SystemAccount

anchor_lang::accounts::system_account::SystemAccount

系统账户，检查账户的拥有者是不是系统程序（即 SystemAccount.info.owner == SystemProgram）。

1
2
3
4
#[derive(Debug, Clone)]
pub struct SystemAccount<'info> {
    info: &'info AccountInfo<'info>,
}

Sysvar

anchor_lang::accounts::sysvar::Sysvar

系统变量，检查账户是否是系统变量。

1
2
3
4
5

pub struct Sysvar<'info, T: solana_program::sysvar::Sysvar> {
    info: &'info AccountInfo<'info>,
    account: T,
}

TODO: 写一篇 post 单独介绍实现了 solana_program::sysvar::Sysvar 的类型。

UncheckedAccount

强调不做任何检查的账户，需要手动在合约指令中做检查。

1
2
#[derive(Debug, Clone)]
pub struct UncheckedAccount<'info>(&'info AccountInfo<'info>);

发表于 更新于

以下是各种索引算法的简要对比表，包括其原理、性能优势、适用场景和缺点。

索引算法 原理介绍 为什么性能高 适用场景 缺点/性能差的场景
B+ 树 B+ 树是一种平衡多叉树，数据仅存储在叶节点，所有叶节点按顺序连接，适合范围查询和顺序访问。 结构层次分明，叶节点通过链表相连，实现快速范围查找和顺序遍历。 适用于数据库索引、大量顺序读取或范围查询的场景。 高维数据或频繁更新的场景性能较差。插入、删除操作复杂，维护成本高。
倒排索引 建立词项到文档的映射关系，将每个词项关联到出现该词的文档列表，通常用于全文搜索。 通过直接访问词项位置，可快速找到包含该词的所有文档。 适用于文本搜索、日志检索等全文检索场景。 对于非文本数据无效，处理频繁更新的文档集时性能较差，占用内存大。
HNSW HNSW 基于分层的小世界图结构，通过近似最近邻的方法实现高效向量检索。 通过多层图索引和邻居节点搜索，实现快速的近似最近邻查找。 适用于向量相似度检索、推荐系统、图像搜索等高维向量场景。 构建和维护图的成本较高，尤其是频繁更新和插入向量的情况下。对高精度要求场景不适合。
跳表（Skip List） 通过多级链表实现快速搜索，每级链表跳过部分节点，提高查找速度。 基于多级链表，可在 O(log n) 时间内查找目标节点。 适用于键值存储、顺序查询需求的场景，作为简单替代结构。 在超大数据集或高频率更新的场景下不够高效，性能会下降。
LSM 树 LSM 树通过分层排序和合并，将数据写入磁盘前缓存在内存，适合高写入量的场景。 数据批量写入减少随机写的开销，分层合并提升读取效率。 适合写密集型的键值数据库，如 RocksDB、LevelDB。 读性能可能较差，特别是大量读操作时，需通过多层合并查询。
Trie 树 用树结构保存字符串的前缀，每个节点代表一个字符，用于高效的前缀匹配。 可以快速定位字符串的前缀路径，适合匹配和自动补全。 适用于自动补全、前缀匹配等需要快速定位前缀的场景。 占用内存较大，无法很好地处理非字符串数据，不适合范围查询。
Annoy 使用多棵随机 KD 树构建索引，用于近似最近邻查询，查询时从多棵树中查找相似点。 随机生成多棵树，提高查找相似度的效率，查询速度快。 适用于低维度、高性能要求的向量检索，推荐系统等。 处理高维数据时性能较差，存储空间需求大。更新不便。
LSH（Locality-Sensitive Hashing） 将相似数据哈希到相同的桶中，快速找到相似数据的近似最近邻索引方法。 通过哈希实现分桶，减少相似数据查询范围，查询速度快。 适用于低维向量的相似性搜索，处理文本等场景。 高维度数据上效率低，近似度精度差，占用较多内存。

简要总结

  • B+ 树 和 倒排索引 是经典的数据库和全文搜索引擎中常用的索引结构，适合关系型数据和文本数据的检索。
  • HNSW 和 Annoy 是面向高维向量的近似最近邻索引结构，常用于推荐系统、语义搜索等场景。
  • LSM 树 适合写密集的场景，如键值数据库。
  • Trie 树 和 跳表 更适合简单的键值存储和字符串匹配，但不适合复杂的数据查询和高维向量检索。
  • LSH 在维度较低的数据上表现较好，但对高维数据表现有限。

发表于 更新于

Why ZKP?

零知识证明 Zero-knowledge Proofs

其中的 Proof($\pi$) 必须是个有用的：$Theorem / Statement / Proposition$

  1. 不要把 Proof 这个词忘掉，到底证明了什么？
  2. 两个角色，证明者（prover）、验证者（verifier），是双方的。写代码的时候要时刻关注写的到底是哪部分，是证明者的代码，还是验证者的代码。

Prover Code: 需要关注，有没有产生一个有效的证明，产生这个证明的时候有没有泄漏不该泄漏的信息。
Verifier Code：关注，这个证明是不是有效的。

写代码的时候容易忘掉。
这是一个 Two-party interaction

  1. 关注以下三个性质：
  • 完备性（Completeness）：诚实的证明者（honest prover）一定能成功证明。
  • 可靠性（Soundness）：恶意的证明者（malicious prover）一定通不过验证。很难测试，需要非常认真、仔细、深入的考虑这个问题：如何保证 verifier 不会被欺骗。
  • 零知识（Zero-knowledge）：恶意的验证者（malicious verifier）无法获得有用的知识。

关注 Meta Theorems (Completeness and Soundness)的证明
如何保证我们写的 babyplonk 是 sound 的。

  • Prover 和 Verifier 之间有大量的交互。Verifier 会发送大量的 challenge 给 Prover。challenge 越多，Proof Size 就越大。
  • 交互过程中的步骤顺序不能调换。
  • 实际项目中如果有安全漏洞是非常严重的。
  • 攻击本身也可能是 ZK 的，不知道谁干的。

Non-interactive

BlockChain 中经常使用 Non-interactive ZKP。 Fiat-Shamir Transformation 能把 public-coin protocol 转换成 non-interactive protocol。

public-coin 指的是掷硬币，公开的发随机数 challenge。
借助 Random Oracle (RO) 工具来辅助 Prover 来产生这些硬币。随机数不一定是由 verifier 作为来源，由可信第三方来提供也可以。
Prover 与 RO 交互，产生证明 $\pi$ 直接发送给 Verifier。不需要等待 Verifier 回复，Verifier 可以在未来异步验证这个证明。
通常使用一个足够安全的哈希函数（Cryptographic Hash Function）来替代 RO 的角色。没有严格的证明，大概率不会出问题。

Commitment

  1. $O(1)$ Size。无论数据多大，比如 10 GB 的文件，都可以产生一个很小的串来代表它。
  2. Binding。$CM(D1)\not ={CM(D2)} \iff D1\not ={D2}$。
  3. Hiding。能够保护数据，可以混入随机数。同一个文件两次 Commit 可以得到不同的 Commitment。

Blockchain： Put commitment on chain （EIP-4844，Rollup-blob）

Commit-and-Prove

alt text

Why zkSNARK

发表于 更新于

这是结诚浩的《图解密码技术》一书的读书笔记，我是在去北京的火车上把其中感兴趣的部分草草过完的。World of Z2O-K7E 只是建议过一下，我就只是过一下，感觉还是很有帮助的，至少看过了之后，我能感觉自己的大脑切换到了“密码学的上下文”，接收零知识证明相关的知识似乎更高效了。

基本常识

  1. 不要使用保密的密码算法（即隐蔽式的安全性），应该使用得到广为验证的公开的密码算法，而保护好密钥。
  2. 使用低强度的密码会给人一种错误的安全感，比不进行加密更危险。
  3. 任何密码总有一天会被破解，除了不实用的一次性密码本和传说中的量子密码。
  4. 密码只是信息安全的一部分，提防“社会工程学”。

对称密码

DES / 3DES

一种将 64 位明文加密为 64 位密文的对称密码算法，需要以分组为单位对输入进行处理（这样的密码算法称为分组密码，block cipher）。DES 已经可以在现实时间内被破解。

三重DES（3DES）是为了增加 DES 的强度设计的。三重 DES 并不是三轮加密，而是加密、解密、加密。如果三轮的密钥都相同，就跟 DES 一样了。

第一轮和第三轮使用同样的密钥则称为 DES-EDE2。
三轮都不同则称为 DES-EDE3。

AES

Rijndael 算法在 2000 年被选为 AES。

分组长度固定为 128 比特，密钥长度有 128、192、256 比特三种。

加密过程：SubBytes -> ShiftRows -> MixColumns -> AddRoundKey

解密过程: AddRoundKey -> InvMixColumns -> InvShiftRows -> InvSubBytes

如何选择

不用 DES，少用 3DES，尽量用 AES。

分组密码的模式

  • ECB（Electronic CodeBook，电子密码本）：简单，快速，支持并行计算；明文中重复排列会反映在密文中，并且通过删除、替换密文分组可以对明文进行操作，对包含某些比特错误的密文解密时对应的分组会出错，不能抵御重放攻击。不要用。
  • CBC（Cipher Book Chaining，密文分组连接模式）：推荐使用，重复的明文不会导致重复的密文，可以解密任意密文分组。必须是先加密再 XOR，如果反过来，则其效果等同于 ECB，可以直接从 IV （初始化向量）开始，依次将前后两组密文执行 XOR，得到的每组结果恰好就等于 ECB 每组的结果。
  • CFB / OFB：不需要填充（padding）。
  • CTR（CounTeR，计数器模式）：推荐使用，主动攻击者反转密文分组中的某些比特时，明文分组中相对应的比特也会被反转。

公钥密码

RSA 的基本步骤：

  1. 取两个比较大的质数 p 和 q。
  2. 求两者的乘积 $N = p \times q$。
  3. 求 ，即 p 和 q 的最小公倍数；有的资料说的是求欧拉函数值 $\phi = (p-1) \times (q-1)$，以下统称 $\phi$。

GPT: 两者都有各自的使用场景，但在实际使用中，求欧拉函数值 ($\phi$) 更为常见。

  1. 选择公钥 $E$，$E$ 与 $\phi$ 互质并且 $1 < E < \phi$。
  2. 求私钥 $D$，$D \times E \equiv 1$ (mod $\phi$)，即 D 为 E 的乘法逆元。
  3. 这样得到公钥为 $(E, N)$，私钥为 $(D, N)$。

一个使用小质数实现的简单的 RSA：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
use num::BigInt;
use rand::seq::index::sample;
use rand::{thread_rng, Rng};

const SMALL_PRIMES: [u64; 50] = [
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
    101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
    197, 199, 211, 223, 227, 229,
];

#[derive(Debug)]
struct KeyPair {
    private_key: u64,
    public_key: u64,
    modulus: u64,
}

impl KeyPair {
    pub fn generate() -> Self {
        let mut rng = thread_rng();
        let indices = sample(&mut rng, SMALL_PRIMES.len(), 2);
        // use crate rand to select two random prime numbers
        let p = SMALL_PRIMES[indices.index(0)];
        let q = SMALL_PRIMES[indices.index(1)];
        let modulus = p * q;
        let phi = (p - 1) * (q - 1);
        let public_key = loop {
            let public_key = SMALL_PRIMES[thread_rng().gen_range(0..SMALL_PRIMES.len())];
            if public_key < phi && gcd(public_key, phi) == 1 {
                break public_key;
            }
        };

        let mut private_key = 1;
        while (public_key * private_key) % phi != 1 {
            private_key += 1;
        }

        Self {
            private_key,
            public_key,
            modulus,
        }
    }

    pub fn encrypt(&self, message: BigInt) -> BigInt {
        message.pow(self.public_key as u32) % self.modulus
    }

    pub fn decrypt(&self, encrypted_message: BigInt) -> BigInt {
        encrypted_message.pow(self.private_key as u32) % self.modulus
    }

    // getters

    pub fn get_private_key(&self) -> (u64, u64) {
        (self.private_key, self.modulus)
    }

    pub fn get_public_key(&self) -> (u64, u64) {
        (self.public_key, self.modulus)
    }

    pub fn get_modulus(&self) -> u64 {
        self.modulus
    }
}

fn gcd(p0: u64, p1: u64) -> u64 {
    let mut p0 = p0;
    let mut p1 = p1;
    while p1 != 0 {
        let temp = p1;
        p1 = p0 % p1;
        p0 = temp;
    }
    p0
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_rsa() {
        for _ in 0..100 {
            let key_pair = KeyPair::generate();
            let message = BigInt::from(rand::thread_rng().gen_range(6..key_pair.get_modulus()));
            let encrypted_message = key_pair.encrypt(message.clone());
            let decrypted_message = key_pair.decrypt(encrypted_message.clone());
            assert_eq!(decrypted_message, message);
            println!(
                "public key: ({}, {}), private key: ({}, {}), message: {}, encrypted: {}, decrypted: {}",
                key_pair.get_public_key().0, key_pair.get_public_key().1,
                key_pair.get_private_key().0, key_pair.get_private_key().1,
                message,
                encrypted_message,
                decrypted_message
            )
        }
    }
}

单向散列函数

单向散列函数（也称为消息摘要函数、哈希函数、杂凑函数），用来保证消息的完整性（integrity），也称为一致性。

输入的消息也称为原像（pre-image）。

输出的散列值也称为消息摘要（message digest）或者指纹（fingerprint）。

难以发现碰撞的性质称为抗碰撞性（collision resistance）。

算法选择

MD5 是不安全的。

SHA-1 不应该用于新用途。

SHA-2 （SHA-256以上） 、SHA-3 是安全的，可以使用。

消息认证码

消息认证码（Message Authentication Code）是一种确认完整性并进行认证的技术。

实现方法

  • 单向散列函数，例如 HMAC。
  • 分组密码，例如 AES-CMAC。
  • 其他，例如流密码和公钥密码。

数字签名

使用公钥密码（比如 RSA、椭圆曲线）来实现。

  • 绝对不要对意思不清楚的消息进行签名，可能无意中解密了公钥加密的密文。
  • 依赖公钥基础设施，公钥必须属于真正的发送者，即使用证书来确认。

密钥交换

Diffie-Hellman

一个使用小质数实现的简单的 Diffie-Hellman：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
use num::BigInt;
use rand::thread_rng;
use rand::Rng;

const P_AND_G: [(u64, u64); 20] = [
    (7, 3),
    (11, 2),
    (13, 2),
    (17, 3),
    (19, 2),
    (23, 5),
    (29, 2),
    (31, 3),
    (37, 2),
    (41, 6),
    (43, 3),
    (47, 5),
    (53, 2),
    (59, 2),
    (61, 2),
    (67, 2),
    (71, 7),
    (73, 5),
    (79, 3),
    (83, 2),
];

// prime P and generator G
#[derive(Debug)]
pub struct PnG {
    prime: u64,
    generator: u64,
}

impl PnG {
    pub fn generate() -> Self {
        let (prime, generator) = P_AND_G[thread_rng().gen_range(0..P_AND_G.len())];
        Self { prime, generator }
    }

    pub fn get_prime(&self) -> u64 {
        self.prime
    }

    pub fn get_generator(&self) -> u64 {
        self.generator
    }

    pub fn generate_random_number(&self) -> u64 {
        // generate a number in the range of 1 to prime - 2
        thread_rng().gen_range(1..self.prime - 2)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_diffie_hellman() {
        for round in 0..10 {
            let pg = PnG::generate();
            println!(
                "{round}) Prime: {}, Generator: {}",
                pg.get_prime(),
                pg.get_generator()
            );
            let alice_number = pg.generate_random_number();
            let bob_number = pg.generate_random_number();
            println!(
                "{round}) Alice number: {}, Bob number: {}",
                alice_number, bob_number
            );
            let alice_partial_key =
                BigInt::from(pg.get_generator()).pow(alice_number as u32) % pg.get_prime();
            let bob_partial_key =
                BigInt::from(pg.get_generator()).pow(bob_number as u32) % pg.get_prime();
            println!(
                "{round}) Alice partial key: {}, Bob partial key: {}",
                alice_partial_key, bob_partial_key
            );
            let alice_full_key =
                BigInt::from(bob_partial_key).pow(alice_number as u32) % pg.get_prime();
            let bob_full_key =
                BigInt::from(alice_partial_key).pow(bob_number as u32) % pg.get_prime();
            println!(
                "{round}) Alice full key: {}, Bob full key: {}",
                alice_full_key, bob_full_key
            );
            assert_eq!(alice_full_key, bob_full_key);
        }
    }
}

椭圆曲线密码

椭圆曲线密码是利用“椭圆曲线上的离散对数问题”的复杂度来实现的。

使用了椭圆曲线的 schnorr 的一个简单实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
use k256::{NonZeroScalar, ProjectivePoint, PublicKey};
use rand::rngs::OsRng;

fn main() {
    // 使用操作系统级别的 RNG
    let mut rng = OsRng;

    // Alice 拥有一个私钥 a，计算公钥 aG
    // 私钥 a
    let a = NonZeroScalar::random(&mut rng);
    // 公钥 aG
    let a_g = ProjectivePoint::from(PublicKey::from_secret_scalar(&a));

    // 知道 G 和 aG，求 a，属于椭圆曲线上的离散对数问题，目前没有有效的解法
    let r = NonZeroScalar::random(&mut rng);
    // Alice 生成一个随机数 r，并计算 R = rG
    let r_g = ProjectivePoint::from(PublicKey::from_secret_scalar(&r));

    // Bob 提供一个挑战 c
    let c = NonZeroScalar::random(&mut rng);

    // Alice 计算响应 z = r + a * c (mod q)
    let ac = a * c; // 计算 a * c
    let z = r.add(&ac);

    let Some(z) = NonZeroScalar::new(z).into() else {
        eprintln!("计算 z 为零。");
        return;
    };

    // Alice 将 z 发送给 Bob，Bob 验证 zG ?= R + c*PK
    let z_g = ProjectivePoint::from(PublicKey::from_secret_scalar(&z));

    // 计算 c  * PK
    let c_pk = a_g * *c;

    // 计算 rG + c*PK
    let r_plus_cpk = r_g + c_pk;

    // 验证 zG ?= rG + c*PK
    // c * PK 与 a * c 的关系是？
    // 为什么这个证明是成立的
    // 为什么这个证明是不可伪造的
    // 回答:
    // c * PK = c * a * G = a * c * G = a * c * G = ac * G
    // PK = aG ?
    if z_g == r_plus_cpk {
        println!("验证成功，Alice 证明了她拥有私钥.");
    } else {
        println!("验证失败.");
    }
}

// 与 GPT 的交谈：
// 为什么 Alice 要先生成一个随机数？
// 答：为了证明她拥有私钥，她需要一个随机数 r，然后计算 R = rG，然后计算 z = r + a * c (mod q)
// 可以让 Bob 先生成随机数并发送给 Alice 吗？（然后 Alice 再生成 r ，发送 rG）
// 答：可以，但是这样会暴露 Bob 的私钥，因为 Bob 会发送 c * PK，PK = aG，所以 Bob 的私钥就会暴露
// 不对啊，Bob 只需要发送 c，不会暴露私钥啊
// 答：对，Bob 只需要发送 c，不会暴露私钥，但是这样会暴露 Bob 的公钥，Bob 的公钥是 aG，这样会暴露 Bob 的身份
// 不对啊，aG 是 Alice 使用私钥 a 计算出来的公钥，怎么会是 Bob 的公钥呢？
// 答：对，我理解错了，Bob 只需要发送 c，不会暴露私钥，也不会暴露公钥，这样是可以的
// Bob 先发送随机数给 Alice 真的没问题吗？Alice 不会获得没有 a 但是证明她拥有 a 的超能力吗？
// 答：Alice 不会获得没有 a 但是证明她拥有 a 的超能力，因为 Alice 需要 a 来计算 z = r + a * c (mod q)，如果没有 a，Alice 就无法计算 z
// Alice 不能用假的 a' 来计算 z 吗？一直用假的 a', 是否也能通过验证？
// 答：不能，因为 Bob 会用 a' 来计算 c * PK，然后验证 zG ?= R + c * PK，如果 a' 是错误的，那么 c * PK 也是错误的，验证就会失败
// PK 和 zG 都是用 a' 计算出来的，所以 Bob 永远都会验证成功，不管 Alice 用了什么 a'，验证都会成功，这样 Alice 是否就获得的超能力
// 答：不会，因为 Alice 无法计算出正确的 z，验证会失败
// z' = r + a' * c (mod q)，所以 z'G = R + c * a' * G 验证肯定成功吧？
// 答：不会，因为 c * a' * G != c * a * G，验证会失败
// 你好像没有理解，如果 Bob 实现发送了挑战 c，Alice 可以使用任何除了 a 之外的密钥替换 a（比如 a')，这样整个流程只是证明了 Alice 拥有一个密钥（这个密钥并不一定是 a）
// 答：对，我理解错了，如果 Bob 先发送了挑战 c，Alice 可以使用任何除了 a 之外的密钥替换 a（比如 a'），这样整个流程只是证明了 Alice 拥有一个密钥（这个密钥并不一定是 a）
// 所以 Alice 即使没有任何密钥，她临时编造一个，在这种情况下，Bob 永远都无法验证 Alice 是否拥有私钥，这样 Alice 就获得了超能力
// 所以顺序不能调换，对吗？
// 答：对，顺序不能调换，Alice 必须先生成一个随机数 r，然后计算 R = rG，然后计算 z = r + a * c (mod q)，然后发送 z 给 Bob，Bob 验证 zG ?= R + c * PK

发表于 更新于

目标

从今天开始，学习零知识证明相关知识，暂定 3 个月（到2024年7月26日完成）的学习目标为：

  1. 完成零知识证明常见算法、实现的学习，至少能够知道它们解决的是什么问题，分别适用于什么业务场景。
  2. 学会并熟练掌握使用至少一个流行的 Rust 零知识证明库。
  3. 参与至少一个零知识证明的(开源?)项目，需要提交有质量的代码。

初步计划

V20240426

  1. 第一个月: World of Z2O-K7E 的学习；产出为“能够在朋友、同事甚至是小学生（如果我有幸能认识一个愿意听我讲的）面前把学到的哲学、原理、应用讲出来，讲清楚”。
  2. 第二个月: 完成 World of Z2O-K7E 的学习并开始学习 Rust 相关库，写 demo；学习产出参考上一个月，写 demo 的产出为能够全面反映该 Rust 库的各种功能的一个 repo。
  3. 第三个月: 继续写 demo，看相关开源项目源码，参与项目；产出物为 项目地址 / commit / PR 记录等等。

介于本人在该领域是完全的“零知识”，以上仅为初步计划，如果有任何修改（即使是放弃）都需要更新本文。

20240530

一个多月了，公司的事有点烦。实际上我话太少，并没有找人验证过我是否能证明我能讲出所有我学到的东西，目前学习进度并不快，只是能够把 RSA 和 schnorr 的流程完整复述出来（并用小质数作为例子介绍）。报了一个课，希望能学到我想学的东西，后面打算整理这个课的笔记了。继续加油！

发表于 更新于

定义

  • $S$、$R$ 为关系模式，$s$、$r$ 为关系实例。
  • 要计算关系除法，需要满足 $S ⊆ R$。
  • 给定一个元组 $t$，令 $t[S]$ 代表元组 $t$ 在 $S$ 中属性上的投影；那么，$r ÷ s$ 是 $R-S$ 模式的一个关系。
  • 元组 $t$ 在 $r ÷ s$ 中的充要条件是满足以下两个：
    1. $t$ 在 $Π_{R-S}(r)$ 中
    2. 对于 $s$ 中的每个元组 $t_s$，在 $r$ 中存在一个元组 $t_r$ 且满足：
      • $t_r[S] = t_s[S]$
      • $t_r[R-S] = t$
  • 例子：

$r$:

A1 A2
a e
a f
b e
b g
c e
c f
d f

$s$:

A2
e
f

$r ÷ s$:

A1
a
c

公式

关系代数除法可以使用其它关系代数运算替代：

用上一节的例子就是：

A1
a
b
c
d
A1 A2
a e
a f
b e
b f
c e
c f
d e
d f

公式中是为了计算差（$-$）的时候两个操作数模式相同，对 $r$ 做了一下模式的颠倒，其实还是 $r$。

A1 A2
a e
a f
b e
b g
c e
c f
d f
A1 A2
b f
d e
A1
b
d
A1
a
c